#!/usr/bin/python
# -*- coding: utf8 -*-

import sys
import os
import pprint

from common import *

symbols = {}
terminal_symbols = set()
reverse_mappings = {}

class Symbol:
    def __init__(self, name):
        self.name = name
        self.rules = []

class Rule:
    def __init__(self, lhs, rhs):
        self.lhs = lhs
        self.rhs = make_tuple(rhs)
    
    def debug_string(self):
        return u'%s->%s' % (self.lhs, u' '.join(self.rhs))


def get_symbol(target):
    if isinstance(target, Symbol):
        return target
    name = target
    if name not in symbols:
        symbols[name] = Symbol(name)
    return symbols[name]


def append_rule(lhs, rhs):
    s = get_symbol(lhs)
    s.rules.append(Rule(s.name, rhs))


def get_assist_symbol(target):
    target = make_tuple(target)
    s = get_symbol(u'#(%s)' % '_'.join(target))
    if len(s.rules) == 0:
        append_rule(s, target)
    return s


def populate_terminal_symbols():
    for s in symbols.values():
        if len(s.rules) == 0:
            terminal_symbols.add(s.name)


def is_terminal(target):
    if isinstance(target, unicode) or isinstance(target, str):
        return target in terminal_symbols
    elif isinstance(target, Symbol):
        return target.name in terminal_symbols
    else:
        return None


# eliminate rules like A->Bw
def eliminate_terminal_rhs():
    for s in symbols.values():
        old_rules = s.rules
        s.rules = []
        for r in old_rules:
            if len(r.rhs) > 1:
                rhs = tuple([get_assist_symbol(item).name if is_terminal(item) else item \
                        for item in r.rhs])
            else:
                rhs = r.rhs
            append_rule(s, rhs)


# eliminate rules like A->B
def eliminate_unit_rules():
    done = False
    while not done:
        done = True
        for s in symbols.values():
            old_rules = s.rules
            s.rules = []
            for r in old_rules:
                if len(r.rhs) == 1 and not is_terminal(r.rhs[0]):
                    done = False
                    rs = get_symbol(r.rhs[0])
                    if rs.name == s.name:
                        continue
                    for rr in rs.rules:
                        append_rule(s, rr.rhs)
                else:
                    append_rule(s, r.rhs)


# eliminate rules like A->BCD
def eliminate_long_rules():
    done = False
    while not done:
        done = True
        for s in symbols.values():
            old_rules = s.rules
            s.rules = []
            for r in old_rules:
                if len(r.rhs) > 2:
                    done = False
                    new_rhs = make_tuple(get_assist_symbol(r.rhs[0:2]).name) \
                            + r.rhs[2:]
                    append_rule(s, new_rhs)
                else:
                    append_rule(s, r.rhs)


def eliminate_redudant_symbols():
    start_symbols = [u'START']
    cover_symbols = set()
    cover_symbols.add(u'START')

    for s in start_symbols:
        for r in get_symbol(s).rules:
            for i in r.rhs:
                if i not in cover_symbols:
                    cover_symbols.add(i)
                    start_symbols.append(i)

    redudant_symbols = set()
    for s in symbols:
        if s not in cover_symbols:
            redudant_symbols.add(s)
    for s in redudant_symbols:
        del symbols[s]

    return None

def eliminate_duplicated_rules():
    for s in symbols.values():
        keys = {}
        for r in s.rules:
            keys[r.rhs] = r
        s.rules = keys.values()


def standardize_rules(): 
    eliminate_terminal_rhs()
    eliminate_unit_rules()
    eliminate_long_rules()
    eliminate_redudant_symbols()
    eliminate_duplicated_rules()


def populate_reverse_mappings():
    for s in symbols.values():
        for r in s.rules:
            if r.rhs not in reverse_mappings:
                reverse_mappings[r.rhs] = []
            reverse_mappings[r.rhs].append(r)

def get_rules_by_rhs(rhs):
    if rhs not in reverse_mappings:
        return None
    else:
        return reverse_mappings[rhs]


def parse_rules(filename):
    file = open(filename, 'r')
    lines = unicode(file.read(), 'gbk').split('\n')
    
    for line in lines:
        if line.count(u'→') != 1 and line.count(u':') != 1:
            continue
        if line.count(u'→') == 1:
            left, right = line.strip().split(u'→');
        else:
            left, right = line.strip().split(u':');
        lhs = left.strip()
        rhs = right.split()

        get_symbol(lhs)
        for item in rhs:
            get_symbol(item)

        append_rule(lhs, rhs)

    populate_terminal_symbols()
    standardize_rules()
    populate_reverse_mappings()


if __name__ == '__main__':
    parse_rules(sys.argv[1])

    for s in symbols.values():
        for r in s.rules:
            print r.debug_string()

    #print '# print reverse_mappings'
    #for rhs in reverse_mappings:
    #    for r in get_rules_by_rhs(rhs):
    #        print '%s<-%s' % (','.join(r.rhs), r.lhs)
